import org.junit.jupiter.api.Test;
import java.util.Arrays;
import java.util.Random;

/**
 * 二分搜索：二分法
 */
public class TestBinarySearch {

    /**
     * 获取有序数组中第一个 >= value 的元素索引
     * 形象记忆：
     *   把数组想象成一个直角三角形，把它二分为左右两区，比较中间值和 value，中间值偏小，抛弃左区，中间值偏大，抛弃右区，剩余区继续二分，直到左右边界相遇
     */
    @Test
    public void test01() {
        // 1. 准备样本
        int[] arr = new int[10];
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            arr[i] = random.nextInt(100);
        }
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        int value = 50;

        // 2. 二分查找
        int L = 0;  // 左边界指针
        int R = 9;  // 右边界指针
        int mid = L + ((R - L) >> 1);  // 中间值指针

        // 左区：[L, mid]    右区：[mid+1, R]
        while (L != R) {  // 当 L R 不相遇
            if (arr[mid] < value) {
                L = mid + 1;  // 抛弃左区
            } else {
                R = mid;  // 抛弃右区
            }
            mid = L + ((R - L) >> 1);
        }

        int index = arr[L] >= value ? L : -1;
        System.out.printf("所求位置=%d%n", index);
    }
}
